#include "mySearch.h"
#include <iostream>
#include <string>


using namespace std;

SSTable::SSTable()
{
	this->length = 0;
	this->origin = NULL;
}

SSTable::SSTable(int length, int* origin)
{
	this->length = length;
	this->origin = new int[length];
	for (int i = 0; i < length; i++) {
		this->origin[i] = origin[i];
	}
}

SSTable::~SSTable()
{

}

int SSTable::getLength()
{
	return this->length;
}

int* SSTable::getOrigin()
{
	return this->origin;
}

void SSTable::setLength(int length)
{
	this->length = length;
}

void SSTable::setOrigin(int* origin)
{
	this->origin = origin;
}

int SSTable::binSearch(int val)
{
	int left = 0;
	int right = this->length-1;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (val < this->origin[mid]) {
			right = mid - 1;
		}
		else if (val > this->origin[mid]) {
			left = mid + 1;
		}
		else {
			return mid;
		}
	}
	return -1;
}

BSTreeNode::BSTreeNode()
{
	data = 0;
	lchild = NULL;
	rchild = NULL;
}

BSTreeNode::BSTreeNode(int data)
{
	this->data = data;
	this->lchild = this->rchild = NULL;
}

BSTreeNode::BSTreeNode(int data, BSTreeNode* lchild, BSTreeNode* rchild)
{
	this->data = data;
	this->lchild = lchild;
	this->rchild = rchild;
}

BSTreeNode::~BSTreeNode()
{

}

int BSTreeNode::getData()
{
	return this->data;
}

BSTreeNode* BSTreeNode::getLChild()
{
	return this->lchild;
}

BSTreeNode* BSTreeNode::getRChild()
{
	return this->rchild;
}

void BSTreeNode::setData(int data)
{
	this->data = data;
}

void BSTreeNode::setLChild(BSTreeNode* lchild)
{
	this->lchild = lchild;
}

void BSTreeNode::setRChild(BSTreeNode* rchild)
{
	this->rchild = rchild;
}

BSTree::BSTree()
{
	num = 0;
	root = NULL;
}

BSTree::BSTree(int num, int* data)
{
	this->num = num;
	this->root = NULL;
	for (int i = 0; i < num; i++) {
		addNode(data[i]);
	}

}

BSTree::~BSTree()
{

}

int BSTree::getNum()
{
	return this->num;
}

BSTreeNode* BSTree::getRoot()
{
	return this->root;
}

void BSTree::setNum(int num)
{
	this->num = num;
}

void BSTree::setRoot(BSTreeNode* root)
{
	this->root = root;
}

void printTemp(BSTreeNode* root, string& result)
{
	if (root == NULL) {
		return;
	}
	result += to_string(root->getData()) + " ";
	printTemp(root->getLChild(), result);
	printTemp(root->getRChild(), result);
}

string BSTree::printTree()
{
	string s;
	printTemp(this->root, s);
	return s;
}

bool BSTree::searchNode(int val) {
	BSTreeNode* current = this->root;
	while (current != NULL) {
		if (current->getData() == val) {
			return true;
		}
		else if (current->getData() < val) {
			current = current->getRChild();
		}
		else {
			current = current->getLChild();
		}
	}
	return false;
}


bool BSTree::addNode(int val)
{
	BSTreeNode* newNode = new BSTreeNode(val);
	if (this->root == NULL) {
		this->root = newNode;
		this->num++;
		return true;
	}
	BSTreeNode* current = this->root;
	BSTreeNode* parent = NULL;

	while (current != NULL) {
		parent = current;
		if (val < current->getData()) {
			current = current->getLChild();
		}
		else if (val > current->getData()) {
			current = current->getRChild();
		}
		else {
			delete newNode;
			return false;
		}
	}

	if (val < parent->getData()) {
		parent->setLChild(newNode);
	}
	else {
		parent->setRChild(newNode);
	}

	this->num++;
	return true;
}

bool BSTree::deleteNode(int val)
{
	BSTreeNode* current = this->root;
	BSTreeNode* parent = NULL;
	bool isLeftChild = false;

	while (current != NULL && current->getData() != val) {
		parent = current;
		if (val < current->getData()) {
			current = current->getLChild();
			isLeftChild = true;
		}
		else {
			current = current->getRChild();
			isLeftChild = false;
		}
	}
	if (current == NULL)
		return false;

	//case1:node to be deleted has no children
	if (current->getLChild() == NULL && current->getRChild() == NULL) {
		if (current == this->root) {
			this->root = NULL;//delete the root node
		}
		else if (isLeftChild) {
			parent->setLChild(NULL);
		}
		else {
			parent->setRChild(NULL);
		}
	}

	//case2:node to be deleted has one child
	else if (current->getRChild() == NULL) {
		if (current == this->root) {
			this->root = current->getLChild();
		}
		else if (isLeftChild) {
			parent->setLChild(current->getLChild());
		}
		else {
			parent->setRChild(current->getLChild());
		}
	}
	else if (current->getLChild() == NULL) {
		if (current == this->root) {
			this->root = current->getRChild();
		}
		else if (isLeftChild) {
			parent->setLChild(current->getRChild());
		}
		else {
			parent->setRChild(current->getRChild());
		}
	}

	//case3:node to be deleted has two children
	else {
		BSTreeNode* p = current->getRChild();
		BSTreeNode* find_parent = NULL;
		BSTreeNode* find = current;

		while (p != NULL) {
			find_parent = find;
			find = p;
			p = p->getLChild();
		}

		if (find != current->getRChild()) {
			find_parent->setLChild(find->getRChild());
			find->setRChild(current->getRChild());
		}

		if (current == this->root) {
			this->root = find;
		}
		else if (isLeftChild) {
			parent->setLChild(find);
		}
		else {
			parent->setRChild(find);
		}

		find->setLChild(current->getLChild());
	}

	delete current;
	num--;
	return true;
}